package codingforgreat.lchot150;

public class Lc322 {
    public int coinChange(int[] coins, int amount) {
        return process(coins,0,amount) == Integer.MAX_VALUE ? -1 :  process(coins,0,amount);
    }
    public int process(int[] coins,int index,int path){
        if(path == 0){
            return 0;
        }
        if (index == coins.length) {
            return path == 0 ? 0 : Integer.MAX_VALUE;
        }
        if(index > coins.length){
            return Integer.MAX_VALUE;
        }
        int ans = Integer.MAX_VALUE;
        for(int zhang = 0;path - zhang * coins[index] >= 0;zhang++){
            int next = process(coins, index + 1, path - zhang * coins[index]);
            if (next != Integer.MAX_VALUE) {
                ans = Math.min(ans, zhang + next);
            }
        }
        return ans;
    }
    // 动态规划
    public int coinChange1(int[] coins, int amount) {
        int[][] dp = new int[coins.length + 1][amount + 1];
        for(int i = 1;i <= amount;i++){
            dp[coins.length][i] = Integer.MAX_VALUE;
        }
        for(int index = coins.length - 1;index >= 0;index--){
            for(int path = 0; path <= amount;path++){
                int ans = Integer.MAX_VALUE;
                for(int zhang = 0;path - zhang * coins[index] >= 0;zhang++){
                    int next =dp[index + 1][path - zhang * coins[index]];
                    if (next != Integer.MAX_VALUE) {
                        ans = Math.min(ans, zhang + next);
                    }
                }
                dp[index][path] = ans;
            }
        }

        return dp[0][amount] == Integer.MAX_VALUE ? -1 :  dp[0][amount];
    }
    public int coinChange2(int[] coins, int amount) {
        int[][] dp = new int[coins.length + 1][amount + 1];
        for(int i = 1;i <= amount;i++){
            dp[coins.length][i] = Integer.MAX_VALUE;
        }
        for(int index = coins.length - 1;index >= 0;index--){
            for(int path = 0; path <= amount;path++){
                dp[index][path] = dp[index + 1][path];
                if (path - coins[index] >= 0
                        && dp[index][path - coins[index]] != Integer.MAX_VALUE) {
                    dp[index][path] = Math.min(dp[index][path], dp[index][path - coins[index]] + 1);
                }
            }
        }

        return dp[0][amount] == Integer.MAX_VALUE ? -1 :  dp[0][amount];
    }
}
